import java.util.Arrays;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/4 10:11
 * @description:
 */
public class Solution1314 {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int[][] prefixSum = new int[mat.length][mat[0].length];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                prefixSum[i][j] = ((j - 1 >= 0) ? prefixSum[i][j - 1] : 0)
                        + ((i - 1 >= 0) ? prefixSum[i - 1][j] : 0)
                        + mat[i][j]
                        - (i - 1 >= 0 && j - 1 >= 0 ? prefixSum[i - 1][j - 1] : 0);
            }
        }
        int[][] res = new int[mat.length][mat[0].length];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                int x1 = Math.max(0, i - k);
                int y1 = Math.max(0, j - k);
                int x2 = Math.min(mat.length - 1, i + k);
                int y2 = Math.min(mat[0].length - 1, j + k);
                res[i][j] = prefixSum[x2][y2]
                        - ((y1 - 1 >= 0) ? prefixSum[x2][y1 - 1] : 0)
                        - ((x1 - 1 >= 0 ? prefixSum[x1 - 1][y2] : 0))
                        + ((x1 - 1 >= 0 && y1 - 1 >= 0) ? prefixSum[x1 - 1][y1 - 1] : 0);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution1314 solution = new Solution1314();
        System.out.println(Arrays.deepToString(solution.matrixBlockSum(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, 1)));
        System.out.println(Arrays.deepToString(solution.matrixBlockSum(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, 2)));
    }
}
